import java.util.Arrays;

/**
 * 416. 分割等和子集
 */
public class No416 {
    private int[] nums;

    /**
     * 1. 递归
     */
    public boolean canPartition1(int[] nums) {
        this.nums = nums;
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false;
        int half = sum / 2;
        return dfs(nums.length - 1, half);
    }

    private boolean dfs(int i, int c) {
        if (i < 0) return c == 0;
        if (c < nums[i]) return dfs(i - 1, c);
        return dfs(i - 1, c) || dfs(i - 1, c - nums[i]);
    }

    /**
     * 2. 迭代
     */
    public boolean canPartition2(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false;

        int n = nums.length;
        int half = sum / 2;
        boolean[][] f = new boolean[n + 1][half + 1];
        f[0][0] = true;

        for (int i = 0; i < n; i++) {
            for (int c = 0; c < half + 1; c++) {
                if (c < nums[i]) f[i + 1][c] = f[i][c];
                else f[i + 1][c] = f[i][c] || f[i][c - nums[i]];
            }
        }
        return f[n][half];
    }

    /**
     * 3. 滚动数组空间优化
     */
    public boolean canPartition3(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false;

        int n = nums.length;
        int half = sum / 2;
        boolean[][] f = new boolean[2][half + 1];
        f[0][0] = true;

        for (int i = 0; i < n; i++) {
            for (int c = 0; c < half + 1; c++) {
                if (c < nums[i]) f[(i + 1) % 2][c] = f[i % 2][c];
                else f[(i + 1) % 2][c] = f[i % 2][c] || f[i % 2][c - nums[i]];
            }
        }
        return f[n % 2][half];
    }

    /**
     * 4. 一维数组空间优化
     */
    public boolean canPartition4(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false;

        int half = sum / 2;
        boolean[] f = new boolean[half + 1];
        f[0] = true;

        for (int num : nums) {
            for (int c = half; c >= num; c--) {
                f[c] = f[c] || f[c - num];
            }
        }
        return f[half];
    }
}
